The goal of this proposal is to develop an improved vaccine for melanoma. To this end, the investigator proposes to increase the ability of vaccines to stimulate CD8+ T cells, which play a critical role in tumor protective immunity. Recent laboratory and animal studies suggest this can be achieved by encapsulating the vaccine into pH-sensitive liposomes that can deliver exogenous antigens into the class I restricted pathway of antigen processing and presentation. The investigator has recently developed a powerful new tool to help achieve this goal: an assay that is sensitive enough to directly measure in peripheral blood vaccine-induced increase in antigen-specific CD8+ T cells directed to defined melanoma antigens, such as MAGE-3 and MART-1. To translate these new developments to the clinic, the investigator proposes a phase I/II clinical trial to investigate: 1) Whether immunization to a polyvalent melanoma vaccine encapsulated into pH-sensitive liposomes can induce a CD8+ T cell response to melanoma cells and to MAGE-3 and MART-1; 2) the optimal dose of liposomes which maximally stimulates this response; 3) the potency of this new vaccine formulation compared to encapsulating vaccine into conventional liposomes, the most potent adjuvant the investigator has studied to date; and 4) the safety of this treatment. Patients with AJCC stage Iib or III melanoma will be randomly allocated to treatment with vaccine encapsulated into different dose levels of pH-sensitive liposomes, or as a control, into conventional liposomes. All liposomes will also contain a small amount of IL-2, which prior studies have shown increases vaccine immunogenicity. Prior to, and at fixed intervals following vaccine immunization, the level of CD8+ T cells to defined melanoma antigens (MAGE-3 and MART-1) in peripheral blood, DTH responses to the vaccine, and antibody responses to individual melanoma antigens will be measured to define the immunopotentiating activity of pH-sensitive liposomes. Toxicity and clinical activity will be followed by conventional procedures. Successful completion of this work will provide a new method to increase the clinical effectiveness of vaccines for melanoma, and more generally for other cancers, by potentiating their ability to induce CD8+ T cell responses.